高考申論題
109年
[資訊處理] 資料結構
第 一 題
📖 題組：
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題： 圖一、無向圖G = (V, E)
四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題： 圖一、無向圖G = (V, E)
對於無向圖G = (V, E)：（12分）
⑴請給出對應的相鄰矩陣M。
⑵以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請由節點a開始，描述此深度優先搜尋所產生的深度優先樹（DF-tree）。
⑴請給出對應的相鄰矩陣M。
⑵以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請由節點a開始，描述此深度優先搜尋所產生的深度優先樹（DF-tree）。
📝 此題為申論題
思路引導 VIP
解答本題分為兩部分：首先，依據圖中節點的連線關係，以英文字母順序排列行列，建構 8x8 的相鄰矩陣（無向圖的矩陣必為對稱矩陣）。其次，進行 DFS 追蹤時，務必嚴格遵守「遇到分岔點時依字母順序挑選尚未拜訪之節點」的規則，並詳細記錄每次前進產生的「樹邊（Tree Edge）」與無路可走時的「回溯（Backtracking）」過程，最後畫出完整的深度優先樹。
🤖
AI 詳解
AI 專屬家教
【解題思路】 本題測驗圖的基礎表示法與走訪演算法。第一子題須將圖轉換為相鄰矩陣；第二子題須利用堆疊（或遞迴）概念執行深度優先搜尋（DFS），並依據題目要求的「字母順序」作為分支選擇條件，以建構出唯一的深度優先樹。 【詳解】
▼ 還有更多解析內容